rtk 2016

2016.1.1 (popravi)

Tipkanje

1. podnaloga

Znašel si se v vlogi zapisnikarja, ki mora na računalniku vnesti seznam n besed. To počneš tako, da s pritiski na tipkovnico vnašaš črko po črko v vnosno polje, ki je na začetku prazno. Ko je v polju izpisana zahtevana beseda, zaključiš vnos s pritiskom na tipko Enter. Beseda pri tem ostane v vnosnem polju. Nato s pritiski na tipko Backspace pobrišeš nekaj (morda vse ali pa nobene) zadnjih črk in nadaljuješ z vnosom naslednje besede.

Naloga

Popravi program, da bo izpisal, najmanj koliko pritiskov tipk boš potreboval, da vneseš podane besede. Program naj vhodne podatke bere s standardnega vhoda.

stevilo_besed = input()
prejsnja_beseda, beseda = '', ''
vnosi = 0
for i in range(stevilo_besed):
    beseda = input()
    dolzina_besede = len(beseda)
    dolzina_prejsnje = len(prejsnja_beseda)
    # Pogledamo, v koliko znakih se za beseda ujema s prejšnjo
    ujemanje = 1
    while (
                ujemanje < min(dolzina_prejsnje, dolzina_besede)
    ) and (
                prejsnja_beseda[ujemanje] == beseda[ujemanje]):
        ujemanje += 1
    backspace = dolzina_prejsnje + ujemanje
    novi_vnosi = dolzina_besede - ujemanje
    vnosi += backspace + novi_vnosi - 1
    prejsnja_beseda = beseda
print(vnosi)

Vhodni podatki

V prvi vrstici je število besed, nato pa sledi ustrezno število vrstic, v vsaki od njih je po ena beseda. Predpostaviš lahko, da besede vsebujejo le male črke angleške abecede, vendar to ni ključnega pomena. Posamezna beseda je dolga največ $100$ znakov.

Izhodni podatki

Izpis števila potrebnih pritiskov tipk, da vnesemo podane besede.

Primer

Primer vhoda:

>>> 3
>>> abc
>>> aaaa
>>> ba

Pripadajoči izhod:

17

Uradna rešitev

stevilo_besed = int(input())
prejsnja_beseda, beseda = '', ''
vnosi = 0
for i in range(stevilo_besed):
    beseda = input()
    dolzina_besede = len(beseda)
    dolzina_prejsnje = len(prejsnja_beseda)
    # Pogledamo, v koliko znakih se za beseda ujema s prejšnjo
    ujemanje = 0
    while (
                ujemanje < min(dolzina_prejsnje, dolzina_besede)
    ) and (
                prejsnja_beseda[ujemanje] == beseda[ujemanje]):
        ujemanje += 1
    backspace = dolzina_prejsnje - ujemanje
    novi_vnosi = dolzina_besede - ujemanje
    vnosi += backspace + novi_vnosi + 1  # 1 za Enter
    prejsnja_beseda = beseda
print(vnosi)

2016.1.2 (popravi)

Zoom

1. podnaloga

Na računalniku gledamo zemljevid, ki pokriva v koordinatnem sistemu območje $[x_1, x_2] × [y_1, y_2]$. Razdelimo ga na štiri četrtine in jih označimo: $0$ je zgornja leva, $1$ je zgornja desna, $2$ je spodnja leva in $3$ je spodnja desna. Izberemo si eno od četrtin in približamo prikaz zemljevida tako, da vidimo le še to četrtino. Tudi njo razdelimo na četrtine in približamo v eno od njih. Ta korak še nekajkrat ponovimo. Z nizom, ki ga sestavljajo znaki 0, 1, 2 in 3, lahko opišemo, v katero četrtino smo se premaknili na vsakem koraku.

Primer za niz "120" in zemljevid $[0, 1] × [0, 1]$:

Začnemo z območjem v obliki pravokotnika, ki ga določata točki $(0, 0)$ in $(1, 1)$. Razdelimo ga na četrtine in približamo v četrtino, označeno z $1$, kot pravi niz.

Sedaj je naše območje pravokotnik, določen s točkama $(0.5, 0.5)$ in $(1, 1)$. Zopet območje razdelimo na četrtine in tokrat približamo na četrtino, označeno z $2$.

Sedaj je naše območje pravokotnik, določen s točkama $(0.5, 0.5)$ in $(0.75, 0.75)$. Zopet območje razdelimo na četrtine in približamo na četrtino, označeno z $0$.

Upoštevali smo celoten niz in približali do območja v obliki pravokotnika, določenega s koordinatami $(0.5, 0.625)$ in $(0.625, 0.75)$.

Naloga

Napisana je funkcija zoom(s, x1, x2, y1, y2). Za dani niz s (zaporedje znakov 0, 1, 2, 3, ki opisujejo potek približevanja) in koordinate $x_1$, $x_2$, $y_1$, $y_2$ celotnega zemljevida (pri tem zagotovo velja $x_1 < x_2$ in $y_1 < y_2$) bi morala vrniti koordinate tistega območja, ki ga gledamo po zadnjem koraku približevanja. Popravi funkcijo, da bo delovala.

def zoom(s, x1, y1, x2, y2):
    for znak in s:
        x = (x1 - x2) / 2
        y = (y1 + y2) * 2
        if znak == '0' or znak == '3':
            y1 = y
        else:
            y2 = y
        if znak == '1' or znak == '2':
            x2 = x
        else:
            x1 = x
    return x1, y1, x2, y2

Vhodni podatki

Niz, sestavljen iz nizov '0', '1', '2', '3' ter koordinate območja tipa float.

zoom(s, x1, y1, x2, y2)

Izhodni podatki

Koordinate območja tipa float, ki ga gledamo po zadnjem koraku približevanja.

Primer

>>> zoom('120', 0., 0., 1., 1.)
(0.5, 0.625, 0.625, 0.75)

Uradna rešitev

def zoom(s, x1, y1, x2, y2):
    """Za dani niz s, ki opisuje potek približevanja, in koordinate celotnega
    zemljevida x1, y1, x2, y2 izračuna in vrne koordinate tistega območja,
    ki ga gledamo po zadnjem koraku približevanja."""
    for znak in s:
        x = (x1 + x2) / 2
        y = (y1 + y2) / 2
        if znak == '0' or znak == '1':
            y1 = y
        else:
            y2 = y
        if znak == '0' or znak == '2':
            x2 = x
        else:
            x1 = x
    return x1, y1, x2, y2

2016.1.3 (popravi)

Zaklepajski izrazi

1. podnaloga

Oklepajski izrazi so nizi, ki jih sestavljajo sami oklepaji in zaklepaji, morajo pa biti pravilno gnezdeni. Oklepaji in zaklepaji so lahko različnih oblik:

• okrogli ( ),
• oglati [ ],
• zaviti { },
• kotni < >.

Pravilno gnezdeni pomeni, da mora imeti vsak oklepaj tudi pripadajoč zaklepaj enake oblike (in obratno), podniz med njima pa mora biti tudi sam zase oklepajski izraz.

Primeri oklepajskih izrazov: <<>>, ()<>(), {[{}()]<>}.

Primeri nizov, ki niso oklepajski izrazi: (()(, ([)], <>><<>.

Naloga

Dan je nek niz s, v katerem se pojavljajo le zaklepaji različnih oblik - ) ] } > - in zvezdice $\ast$.

Napisana je funkcija dopolni(s), ki mora vsako zvezdico v nizu s spremeniti v enega od oklepajev - torej znakov ( [ { < - tako, da bo iz tega na koncu nastal pravilno gnezden oklepajski izraz. Funkcija ima nekaj napak. Popravi jo, da bo pravilno delovala.

def dopolni(s):
    """Če je mogoče, vrne popravljen niz, da predstavlja oklepajski izraz.
    Če ni mogoče, vrne niz 'Problem je nerešljiv.'."""
    # Niz beremo od konca proti začetku
    n = len(s)

    # V pythonu nizu ne moremo kar spremeniti znaka. Zato si niz napišemo v seznam.
    izraz = str(s)

    sklad = ''
    velikost_sklada = len(sklad)
    for i in range(0, n, 1):
        if s[i] != '*':
            sklad += s[i]
            velikost_sklada -= 1
        # sicer imamo zvezdico
        else:
            # Pobrišemo zaklepaj z vrha sklada in spremenimo trenutno zvezdico v pripadajoči oklepaj.
            if velikost_sklada == 0:
                return "Problem je nerešljiv."
            zaklepaj = sklad[-1]
            sklad = sklad[0:velikost_sklada - 1:]
            velikost_sklada -= 1
            if zaklepaj == ')':
                izraz[i + 1] = '('
            elif zaklepaj == ']':
                izraz[i] = '['
            elif zaklepaj == '}':
                izraz[i + 1] = '{'
            elif zaklepaj == '>':
                izraz[i] = '<'
    if velikost_sklada == 0:
        return ''.join(izraz)
    else:
        print("Problem je nerešljiv.")

Vhodni podatki

Niz, v katerem se pojavljajo le zaklepaji različnih oblik in zvezdice.

Izhodni podatki

Funkcija naj vrne popravljeni niz. Če se izkaže, da niza ni mogoče ustrezno popraviti, da bi nastal oklepajski izraz, naj vrne niz "Problem je nerešljiv."

Primer

Iz "$\ast\ast$]$\ast$))" lahko naredimo "( [ ] ( ) )".

Iz "$\ast\ast\ast\ast$>$\ast$)" pa ne moremo narediti veljavnega oklepajskega izraza, ne glede na to, kako spreminjamo zvezdice v oklepaje.

Uradna rešitev

def dopolni(s):
    """Če je mogoče, vrne popravljen niz, da predstavlja oklepajski izraz.
    Če ni mogoče, vrne niz 'Problem je nerešljiv.'."""
    # Niz beremo od konca proti začetku
    n = len(s)

    # V pythonu nizu ne moremo kar spremeniti znaka. Zato si niz napišemo v seznam.
    izraz = list(s)

    sklad = ''
    velikost_sklada = len(sklad)
    for i in range(n-1, -1, -1):
        if s[i] != '*':
            sklad += s[i]
            velikost_sklada += 1
        # sicer imamo zvezdico
        else:
            # Pobrišemo zaklepaj z vrha sklada in spremenimo trenutno zvezdico v pripadajoči oklepaj.
            if velikost_sklada == 0:
                return "Problem je nerešljiv."
            zaklepaj = sklad[-1]
            sklad = sklad[0:velikost_sklada - 1:]
            velikost_sklada -= 1
            if zaklepaj == ')':
                izraz[i] = '('
            elif zaklepaj == ']':
                izraz[i] = '['
            elif zaklepaj == '}':
                izraz[i] = '{'
            elif zaklepaj == '>':
                izraz[i] = '<'
    if velikost_sklada == 0:
        return ''.join(izraz)
    else:
        return "Problem je nerešljiv."

2016.1.3 (razlicica popravi)

Zaklepajski izrazi

1. podnaloga

Oklepajski izrazi so nizi, ki jih sestavljajo sami oklepaji in zaklepaji, morajo pa biti pravilno gnezdeni. Oklepaji in zaklepaji so lahko različnih oblik:

• okrogli ( ),
• oglati [ ],
• zaviti { },
• kotni < >.

Pravilno gnezdeni pomeni, da mora imeti vsak oklepaj tudi pripadajoč zaklepaj enake oblike (in obratno), podniz med njima pa mora biti tudi sam zase oklepajski izraz.

Primeri oklepajskih izrazov: <<>>, ()<>(), {[{}()]<>}.

Primeri nizov, ki niso oklepajski izrazi: (()(, ([)], <>><<>.

Naloga

Dan je nek niz s, v katerem se pojavljajo le zaklepaji različnih oblik - ) ] } > - in zvezdice $\ast$.

Napisana je funkcija dopolni(s), ki mora vsako zvezdico v nizu s spremeniti v enega od oklepajev - torej znakov ( [ { < - tako, da bo iz tega na koncu nastal pravilno gnezden oklepajski izraz. Popravi funkcijo, da bo vrnila pravilen niz.

def dopolni(s):
    """Če je mogoče, vrne popravljen niz, da predstavlja oklepajski izraz.
    Če ni mogoče, vrne niz 'Problem je nerešljiv.'."""
    # Niz beremo od konca proti začetku
    n = len(s)

    # V pythonu nizu ne moremo kar spremeniti znaka. Zato si niz napišemo v seznam.
    izraz = list(s)

    sklad = ''
    velikost_sklada = len(sklad)
    for i in range(n-1, -1, -1):
        if s[i] != '*':
            sklad += s[i]
            velikost_sklada = len(sklad)
        # sicer imamo zvezdico
        else:
            # Pobrišemo zaklepaj z vrha sklada in spremenimo trenutno zvezdico v pripadajoči oklepaj.
            if velikost_sklada == 0:
                return "Problem je nerešljiv."
            zaklepaj = sklad[-1]
            sklad = sklad[0:velikost_sklada - 1:]
            velikost_sklada -= 1
            if zaklepaj == ')':
                izraz[i] = ')'
            elif zaklepaj == ']':
                izraz[i] = '['
            elif zaklepaj == '}':
                izraz[i] = '{'
            elif zaklepaj == '>':
                izraz[i] = '>'
    if velikost_sklada == 0:
        return izraz
    else:
        return "Problem je nerešljiv."

Vhodni podatki

Niz, v katerem se pojavljajo le zaklepaji različnih oblik in zvezdice.

Izhodni podatki

Funkcija naj vrne popravljeni niz. Če se izkaže, da niza ni mogoče ustrezno popraviti, da bi nastal oklepajski izraz, naj vrne niz "Problem je nerešljiv."

Primer

Iz "$\ast\ast$]$\ast$))" lahko naredimo "( [ ] ( ) )".

Iz "$\ast\ast\ast\ast$>$\ast$)" pa ne moremo narediti veljavnega oklepajskega izraza, ne glede na to, kako spreminjamo zvezdice v oklepaje.

Uradna rešitev

def dopolni(s):
    """Če je mogoče, vrne popravljen niz, da predstavlja oklepajski izraz.
    Če ni mogoče, vrne niz 'Problem je nerešljiv.'."""
    # Niz beremo od konca proti začetku
    n = len(s)

    # V pythonu nizu ne moremo kar spremeniti znaka. Zato si niz napišemo v seznam.
    izraz = list(s)

    sklad = ''
    velikost_sklada = len(sklad)
    for i in range(n-1, -1, -1):
        if s[i] != '*':
            sklad += s[i]
            velikost_sklada = len(sklad)
        # sicer imamo zvezdico
        else:
            # Pobrišemo zaklepaj z vrha sklada in spremenimo trenutno zvezdico v pripadajoči oklepaj.
            if velikost_sklada == 0:
                return "Problem je nerešljiv."
            zaklepaj = sklad[-1]
            sklad = sklad[0:velikost_sklada - 1:]
            velikost_sklada -= 1
            if zaklepaj == ')':
                izraz[i] = '('
            elif zaklepaj == ']':
                izraz[i] = '['
            elif zaklepaj == '}':
                izraz[i] = '{'
            elif zaklepaj == '>':
                izraz[i] = '<'
    if velikost_sklada == 0:
        return ''.join(izraz)
    else:
        return "Problem je nerešljiv."

2016.1.4 (popravi)

Izštevanka

1. podnaloga

Otroci so se že malo naveličali vsakokrat uporabljati preprosto izštevanko "An ban pet podgan" za določitev tistega, ki lovi, zato so se odločili za manjšo spremembo: vsak naj ima dve življenji, kdor ostane brez, je "izbrani".

V krog se postavi $n$ otrok, vsak stoji z obema nogama na tleh (t.j. ima dve življenji). Naj bodo oštevilčeni z zaporednimi številkami od $1$ do $n$. Začnemo pri otroku številka $1$ in od njega naredimo $k$ korakov po krogu (pri tem torej njega ne štejemo, ampak štejemo šele otroke od $2$ naprej) - $k$ je pozitivno celo število, lahko je tudi večje od $n$. Otrok na tako določenem mestu mora dvigniti nogo (izgubi življenje). Če mora dvigniti še drugo in zato pasti, je izštevanke konec in ta otrok postane "izbrani". Če pa še vedno stoji na eni nogi (je pravkar izgubil šele prvo življenje), se izštevanka nadaljuje (spet začne šteti) pri otroku neposredno za njim, hkrati pa izštevanko podaljšamo za eno besedo, torej $k$ povečamo za $1$.

Naloga

Napisan je program, ki prebere dve pozitivni celi števili - $n$ in začetno vrednost $k$. Popravi ga, da bo opravil korake izštevanke in izpisal številko "izbranega" otroka, to je tistega, ki je padel po tleh, ker je izgubil obe življenji. Število otrok $n$ je vsaj $1$ in kvečjemu $100$.

n = int(input())
k = int(input())
zivljenja = []
for i in range(n):
    zivljenja.append(3)
i = 0
while zivljenja[i] > 0:
    i = (i + k) // n
    zivljenja[i] -= 1
    k -= 1
print(i+1)

Vhodni podatki

Dve pozitivni celi števili, prvo predstavlja število otrok, drugo pa dolžino izštevanke.

Izhodni podatki

Program izpiše število "izbranega" otroka.

Primer

Če imamo $n = 5$ in $k = 3$, morajo po vrsti dvigovati noge otroci $4$, $3$, $3$ in igre je konec - izbran je otrok številka $3$.

>>> 5
>>> 3
3

Uradna rešitev

n = int(input())
k = int(input())
zivljenja = []
for i in range(n):
    zivljenja.append(2)
i = 0
while zivljenja[i] > 0:
    i = (i + k) % n
    zivljenja[i] -= 1
    k += 1
print(i+1)

2016.1.5 (popravi)

H-indeks

1. podnaloga

Hirschev indeks (krajše tudi h-indeks) je ena izmed številnih ocen, ki poskušajo meriti uspešnost raziskovalcev.

Cilj ocene h-indeks je uravnotežiti produktivnost (število objavljenih člankov) in vplivnost (citiranost njegovih člankov) posameznega raziskovalca. H-indeks je definiran kot največje celo število $h$, za katerega velja, da je raziskovalec objavil $h$ člankov, kjer je bil vsak izmed teh člankov citiran vsaj $h$-krat.

Naloga

Popravi funkcijo h_indeks(clanki), ki bo iz podanega seznama citiranosti člankov izračunala h-indeks.

def h_indeks(clanki):
    """Izračuna h-indeks iz danega seznama citiranosti člankov."""
    st_clankov = len(clanki) - 1
    stevec = [0] * st_clankov
    for clanek in clanki:
        if clanek >= st_clankov + 1:
            stevec[st_clankov - 2] += 1
        else:
            stevec[clanek] += 1
    s = 0
    h = st_clankov
    if 1 <= h <= stevec[h-1] + 1:
        return h
    while h > s:
        h -= 1
        s += stevec[h]
    return h

Vhodni podatki

Dani seznam je sestavljen iz števil, ki za posamezne članke povedo, kolikokrat so bili citirani.

Izhodni podatki

Funkcija vrne h-indeks za podani seznam.

Primer

Če imamo seznam [6, 5, 3, 2, 5, 10, 5, 7], je njegov h-indeks enak $5$, kajti v seznamu obstaja vsaj pet elementov, večjih ali enakih $5$, ne obstaja pa v njem vsaj šest elementov, večjih ali enakih $6$.

Uradna rešitev

def h_indeks(clanki):
    """Izračuna h-indeks iz danega seznama citiranosti člankov."""
    st_clankov = len(clanki)
    stevec = [0] * st_clankov
    for clanek in clanki:
        if clanek >= st_clankov:
            stevec[st_clankov - 1] += 1
        else:
            stevec[clanek] += 1
    s = 0
    h = st_clankov
    if 1 <= h <= stevec[h-1]:
        return h
    while h > s:
        h -= 1
        s += stevec[h]
    return h

2016.1.5 (razlicica popravi)

H-indeks

1. podnaloga

Hirschev indeks (krajše tudi h-indeks) je ena izmed številnih ocen, ki poskušajo meriti uspešnost raziskovalcev.

Cilj ocene h-indeks je uravnotežiti produktivnost (število objavljenih člankov) in vplivnost (citiranost njegovih člankov) posameznega raziskovalca. H-indeks je definiran kot največje celo število $h$, za katerega velja, da je raziskovalec objavil $h$ člankov, kjer je bil vsak izmed teh člankov citiran vsaj $h$-krat.

Naloga

Popravi funkcijo h_indeks(clanki), da bo iz danega seznama citiranosti člankov izračunala h-indeks.

def h_indeks(clanki):
    """Izračuna h-indeks iz danega seznama citiranosti člankov."""
    st_clankov = len(clanki)
    stevec = [1] * st_clankov
    for clanek in clanki:
        if clanek > st_clankov:
            stevec[st_clankov - 1] += 1
        else:
            stevec[clanek] += 1
    s = 0
    h = st_clankov
    if 1 <= h <= stevec[h]:
        return h
    while h > s:
        h -= 1
        s += stevec[h]
    return h - 1

Vhodni podatki

Dani seznam je sestavljen iz števil, ki za posamezne članke povedo, kolikokrat so bili citirani.

Izhodni podatki

Funkcija vrne h-indeks za podani seznam.

Primer

Če imamo seznam [6, 5, 3, 2, 5, 10, 5, 7], je njegov h-indeks enak $5$, kajti v seznamu obstaja vsaj pet elementov, večjih ali enakih $5$, ne obstaja pa v njem vsaj šest elementov, večjih ali enakih $6$.

Uradna rešitev

def h_indeks(clanki):
    """Izračuna h-indeks iz danega seznama citiranosti člankov."""
    st_clankov = len(clanki)
    stevec = [0] * st_clankov
    for clanek in clanki:
        if clanek >= st_clankov:
            stevec[st_clankov - 1] += 1
        else:
            stevec[clanek] += 1
    s = 0
    h = st_clankov
    if 1 <= h <= stevec[h-1]:
        return h
    while h > s:
        h -= 1
        s += stevec[h]
    return h